import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ret = new int[numCourses];
        int index = 0;
        // 1. 创建一个数组，用于存放入度
        //    创建一个哈希表用于存放邻接表
        int[] in = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 2. 创建图
        for(int i = 0; i < prerequisites.length; i++){
            // a -> b
            int b = prerequisites[i][0];
            int a = prerequisites[i][1];
            if(!map.containsKey(a)){
                map.put(a, new ArrayList<Integer>());
            }
            map.get(a).add(b);
            in[b]++;
        }

        // 3. 所有入度为0的课程进队
        //    BFS
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(in[i] == 0){
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()){
            int course = queue.poll();
            ret[index++] = course;
            // 遍历邻接表 删除边 i : b c d
            for(int i : map.getOrDefault(course, new ArrayList<Integer>())){
                in[i]--;
                if(in[i] == 0){
                    queue.offer(i);
                }
            }
        }

        // 4. 判断结果
        if(index != numCourses){
            return new int[] {};
        }
        return ret;
    }
}